/**
 * 
 */
package cn.edu.ustc.multicore.exercise.ch2;

import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.Future;
import java.util.concurrent.RecursiveAction;
import java.util.concurrent.TimeUnit;

import cn.edu.ustc.multicore.exercise.ch1.PrimeSearching;

/**
 * @author dragon
 * 
 */
public class PrefixSum extends RecursiveAction {
	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	BtNode node = null;
	int[] output;

	PrefixSum(BtNode node, int[] output) {
		this.node = node;
		this.output = output;
	}

	/**
	 * sum fromleft value
	 */
	@Override
	protected void compute() {
		if (node != null) {
			if (node.getLchild() == null)
				output[node.getLow()] = node.getSum() + node.getFromleft();
			else {
				node.getLchild().setFromleft(node.getFromleft());
				if (node.getRchild() != null)
					node.getRchild().setFromleft(
							node.getFromleft() + node.getLchild().getSum());
				PrefixSum left = new PrefixSum(node.getLchild(), output);
				PrefixSum right = new PrefixSum(node.getRchild(), output);
				left.fork();
				right.compute();
			}
		} else {
			return;
		}
	}

	/**
	 * 
	 * @param input
	 * @return
	 */
	private static int[] sequentiallyPrefixSum(int[] input) {
		int[] output = new int[input.length];
		output[0] = input[0];
		for (int i = 1; i < input.length; i++){
			output[i] = output[i - 1] + input[i];
		}
		return output;
	}

	/**
	 * Generate input array randomly
	 * 
	 * @param length
	 * @return
	 */
	private static int[] RandomGenArray(int length, int bound) {
		System.out
				.println("Generating input[] randomlly, and its unit number between [0 ~ "
						+ bound + "]");
		System.out.println("input[" + length + "]=[");
		int[] numbers = new int[length];
		int max = bound;
		for (int i = 1; i <= length; i++) {
			int seed = (int) Math.round(Math.random() * max);
			numbers[i - 1] = seed;
			if (i >= 20 && i % 20 == 0)
				System.out.println(numbers[i - 1]);
			else
				System.out.print(numbers[i - 1]);
			if (i < numbers.length) {
				System.out.print(",");
			}
		}
		System.out.println("]");
		return numbers;
	}

	/**
	 * 
	 * @param start
	 * @param end
	 * @param count
	 * @param usedTime
	 */
	public static void printResult(int[] input, int[] output, String method,
			long usedTime) {
		System.out.println("the result of Prefix sum as below: ");
		System.out.println("---------------------------------------");
		System.out.println("-> used Algorithm: " + method);
		System.out.println("-> the input:=[");
		for (int i = 1; i <= input.length; i++) {
			if (i >= 20 && i % 20 == 0)
				System.out.println(input[i - 1]);
			else
				System.out.print(input[i - 1]);
			if (i < input.length) {
				System.out.print(",");
			}
		}
		System.out.println("]");
		System.out.println("-> used time(ms): " + usedTime);
		System.out.println("-> the output=[");
		for (int i = 1; i <= output.length; i++) {
			if (i >= 20 && i % 20 == 0)
				System.out.println(output[i - 1]);
			else
				System.out.print(output[i - 1]);
			if (i < output.length) {
				System.out.print(",");
			}
		}
		System.out.println("]");
		System.out.println("---------------------------------------\n\n");
	}

	public static void main(String[] args) throws InterruptedException,
			ExecutionException {
		// default length of input array
		int length = 100;
		// default number bound
		int bound = 100;
		// parse the parameter, and assign them
		if (args != null & args.length > 0) {
			boolean correct = true;
			for (int i = 0; i < args.length; i++) {
				if ("-length".equals(args[i])) {
					if (args[i + 1] != null) {
						length = Integer.valueOf(args[i + 1]);
						i++;
						continue;
					} else {
						correct = false;
						break;
					}
				}

				if ("-bound".equals(args[i])) {
					if (args[i + 1] != null) {
						bound = Integer.valueOf(args[i + 1]);
						i++;
						continue;
					} else {
						correct = false;
						break;
					}
				}
				correct = false;
				break;

			}

			if (!correct) {
				System.out.println("Usage: " + PrimeSearching.class.getName()
						+ " -length number -bound number ");
				return;
			}
		}
		// init input array
		 int[] input = RandomGenArray(length, bound);
//		int[] input = new int[] { 6, 4, 16, 10, 16, 14, 2, 8 };
		String method = null;

		/**
		 * Sequentially Prefix-Sum Algorithm
		 */
		long startTime = System.currentTimeMillis();
		// sequentially prefix sum a input array[]
		method = "Sequentially Prefix-Sum";
		int[] output = sequentiallyPrefixSum(input);
		long endTime = System.currentTimeMillis();
		long usedSecond = endTime - startTime;
		printResult(input, output, method, usedSecond);

		/**
		 * Parallel Prefix-Sum Algorithm
		 * 
		 */

		method = "Parallel Prefix-Sum";
		startTime = System.currentTimeMillis();
		ForkJoinPool fjpool = new ForkJoinPool();
		// step 1. build binary tree from input[]
		PrefixSumInitTreeTask task = new PrefixSumInitTreeTask(input, 0,
				input.length);
		Future<BtNode> result = fjpool.submit(task);
		if(result.isDone()){
			fjpool.shutdown();
			fjpool.awaitTermination(300, TimeUnit.SECONDS);
		}
		BtNode root = result.get();
		root.setFromleft(0);
		int[] output2 = new int[input.length];
		// step 2. compute fromleft value from binary tree root to leave
		PrefixSum action = new PrefixSum(root, output2);
		fjpool.invoke(action);
		endTime = System.currentTimeMillis();
		usedSecond =  endTime - startTime ;
		printResult(input, output2, method, usedSecond);

	}

}
